1. Field of the Invention
The present invention relates to routing protocols, in particular creation of a network topology according to a directed acyclic graph, for establishment of an ad hoc mobile network by mobile routers, where the routing protocols are optimized for minimal overhead for accommodating rapid topology changes in the ad hoc mobile network.
2. Description of the Related Art
Proposals have been made by Internet Engineering Task Force (IETF) groups for improved mobility support of Internet Protocol (IP) based mobile devices (e.g., laptops, IP phones, personal digital assistants, etc.) in an effort to provide continuous Internet Protocol (IP) based connectivity. The IETF has a Mobile IP Working Group that has developed routing support to permit IP nodes (hosts and routers) using either IPv4 or IPv6 to seamlessly “roam” among IP subnetworks. In addition, the Mobile Networks (MONET) group (renamed as the Network Mobility (NEMO) group) has published different Internet Drafts, including an Internet Draft by Thierry Ernst, entitled “Network Mobility Support Terminology”, February 2002. An objective of NEMO is providing mobile nodes with protocols for establishing connectivity with a wide area network, such as the Internet. Thus, mobile routers have been used to establish a mobile network topology in order to route packets between the mobile network and the Internet via a gateway at an edge of the mobile network.
Unfortunately, existing Internet-based routing protocols that assume a persistent connection to a wide area network such as the Internet rely on the ability to aggregate reachability to IP nodes, where all nodes sharing a common network link (such as a link of a top level mobile router connecting to an attachment router on the Internet) share the same routing prefix. Such aggregation creates a hierarchy of network prefixes that enables scalability. However, such a hierarchy is not possible in ad hoc networks.
The IETF has a Mobile Ad-hoc Networks (MANET) Working Group that is working to develop standardized MANET routing specification(s) for adoption by the IETF. According to the MANET Working Group, the “mobile ad hoc network” (MANET) is an autonomous system of mobile routers (and associated hosts) connected by wireless links—the union of which form an arbitrary graph. The routers are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the larger Internet.
The MANET system is particularly suited to low-power radio networks that may exhibit an unstable topology, where wireless propagation characteristics and signal quality between a wireless transmission source and a receiver can be difficult to model and quantify. In a MANET, the device address is tied to the device, not a topological location, as there is no fixed network infrastructure. When the addressed device moves, therefore, the motion changes the routing infrastructure. Hence, as described in an Internet Draft by Baker, entitled “An Outsider's View of MANET”(Mar. 17, 2002), the fundamental behavior of a MANET is that a routing node carries with it an address or address prefix, and when it moves, it moves the actual address; when this happens, routing must be recalculated in accordance with the new topology. For example, each mobile router retains its address prefix; hence, neighboring mobile routers in a MANET may have distinct address prefixes.
Existing MANET protocols focus on the internal connectivity within the unstable topology between mobile devices. MANET protocols can be divided into the following types: stateful (proactive); and stateless (reactive). Proactive MANET protocols distribute routing information throughout the MANET network, enabling the routers within the MANET network to store route information before a data packet needs to be routed; hence, a router determines how to forward a packet based on accessing routing information from an internal table. However, proactive protocols suffer the disadvantage of requiring update messages to update obsolete route entries: the necessity for update messages increases with a corresponding desire for an improvement in route optimization.
Proactive MANET protocols can be subdivided into two subtypes, or “families”: Optimized Routing Approach (ORA), and Least Overhead Routing Approach (LORA). The ORA type protocols are similar to routing protocols used in the Internet, in that they stress maintaining the best states to maintain the shortest path routes, at the expense of requiring more control messages to exchange routes. An example of an ORA type routing protocol is Open Shortest Path First (OSPF) (as specified by the IETF Request for Comments (RFC) 2178), or Intermediate System-to-Intermediate System (IS-IS) protocol (specified by the International Organization for Standardization document ISO 10589). The OSPF protocol involves mobile routers sending link-state advertisements (LSAs) every 3600 sec, enabling resulting in substantial burdens in distributing the LSAs.
FIG. 1 is a diagram illustrating a conventional layer 2 mesh network 10 having multiple mobile routers (N0, N1, N2, N3, N4, . . . N11) interconnected by links (L1, L2, L3, L4, . . . L24) having respective metrics (i.e., costs). For example, the mobile routers N0 and N1 are directly connected via a link L1 (e.g., a wireless IEEE 802.11g link) having a cost of “1”; in contrast, the mobile routers N0 and N9 are directly connected via a wireless link L9 having a corresponding cost of “3”. A routing protocol such as OSPF is needed in order for each mobile router (e.g., N0) to determine a path to a given destination (e.g., N11).
FIG. 2 is a diagram illustrating a Shortest Path First (SPF) routing protocol that is executed by a mobile router of FIG. 1 (e.g., N0) to establish a topology tree 12, illustrated in FIG. 5. SPF relies on a global synchronization of topology databases between the mobile routers, and a global understanding of the associated values metrics encountered by the different mobile routers: each mobile router (e.g., N0) computes a consistent loop less path towards each possible destination.
Hence, the topology tree 12 generated by the mobile router N0 enables the mobile router N0 to send packets to an identified destination (e.g., N11) via a shortest path (e.g., links L5 and L10). As described in detail below, the topology tree 12 is generated based on the SPF computation by the mobile router N0 preserving only the shortest path(s) to a given destination; in contrast, other routing protocols (e.g., BGP, EIGRP) can propose unequal cost load balancing.
As illustrated in FIG. 2, the mobile router (e.g., N0) executes the SPF routing protocol based on establishing in step 14 a network node set (N) that identifies the domain of nodes within the network 10 (i.e., N={N0, N1, N2, . . . N11}) based on received link state advertisement messages from nodes (e.g., N1, N2, . . . N11) throughout the network. The mobile router N0 also establishes in step 16 an adjacent node set A that identifies adjacent node pairs, link identifiers, and costs, based on the received link state advertisement messages from other nodes throughout the network 10. In particular, the adjacent node set A identifies nodes with potential adjacencies and includes, for every node[i] in N (e.g., N0), at least one adjacent node[j], a corresponding link identifier (e.g., L1), and a corresponding cost (i.e., metric) for the link (i.e., A={node[i] in N, {{node[i], link identifier, cost, node[j] in N}}}). Hence, the network node set N and the adjacent node set A represent the link state of the mesh network 10 of FIG. 1.
The mobile router N0 initializes the SPF computation in step 18 by initially inserting within a set K (defined as storing chosen nodes) only the mobile router N0 performing the computation (i.e., the “origin node”) (N0 ∈ K), and emptying the set P that defines chosen paths (P={ }). The set P is configured for storing: path cost; the source node in K, the destination node in K, and the link identifier(s) between the source and destination nodes (i.e., P={path cost, {node in K, {identifier, node in K}*}}}).
The mobile router N0 also initializes in step 18 by initially populating a set C with paths of nodes that are adjacent to the origin node N0. A set C is defined as storing an ordered-by-path-cost of candidate paths C, and contains the following elements: path cost, source node in K, the destination node in N, and the link identifier(s) between the source and destination nodes (i.e., C={path cost, {node in K, {identifier, node in N}*}}}). Hence, the set C is initially populated with the paths from the mobile router N0 to the mobile routers N1, N2, N3, N4, N5, N6, N7, N9, as illustrated by the added entries 20 of FIG. 3. In particular, FIG. 3 is a diagram illustrating the insertion and deletion of candidate paths in set C during execution of the method of FIG. 2; hence, entries 20 are added to the empty set C in step 18.
The mobile router N0 begins the SPF computation in step 22 of FIG. 2 by selecting another node for SPF computation (i=1): the mobile router N0 begins by selecting an adjacent node (i.e., AN) as the next node for analysis (e.g., AN[i=1]=N1). The mobile router N0 selects and removes from the set C the least cost path (Least_Path[i]) for the selected adjacent node AN[i=1] (e.g., N1) in step 24, illustrated in FIG. 3 as the removal of the corresponding entry by the line 24a removing the entry for the link L1 between nodes N0 and N1 at a cost of “1”
If in step 26 of the selected adjacent node AN[i=1] (e.g., N1)is not already a member of the set K, the mobile router NO adds in step 28 the selected adjacent node AN[i=1] to the set K of chosen nodes (N1 ∈ K), and adds the least cost path Least_Path[i] to the set P of FIG. 4, for example as entry 28a. The mobile router N0 then extends the path Least_Path[i] from the origin node N0 beyond the selected adjacent node AN[i=1] by adding in steps 30, 32, 34, 36, and 38 to the set C links to any secondary adjacent nodes (SAN) that are adjacent to the selected adjacent node AN[i=1] and that are not already members of the set K.
In particular, for each secondary adjacent node SAN[j] relative to the selected adjacent node AN[i=1] (e.g., N1), if in step 32 the secondary adjacent node SAN[j] (e.g., N2, N5, or N11) is not already in the set K, then: the path from the origin N0 to the selected adjacent node AN[i=1] (e.g., N1) is extended in step 34 to the secondary adjacent node SAN[j] by adding the corresponding link and cost for reaching the secondary adjacent node SAN[j]; the extended path is stored in step 36 in set C as a candidate path, and the steps 30, 32, 34, and 36 are repeated for the next secondary adjacent node. Hence, as illustrated in FIG. 3, the extension of the paths from the origin node N0 beyond the selected adjacent node AN[i=1] (e.g., N1) causes the addition of entries 36a for the secondary adjacent nodes (e.g., N2, N5, N11) associated with the selected adjacent node AN[i=1] (e.g., N1).
The mobile router N0 then repeats in step 40 the process for the next adjacent node AN[i=i+1] (e.g., N2), repeating steps 24, 26, 28, 28, 30, 32, 34, 36, and 38 for each of the nodes (N2, N3, N4, . . . N11). In particular, during computation of the node AN[i=2] (e.g., N2), the corresponding least cost path Least_Path[i=2] is deleted from set C in FIG. 3 in step 24 (event 24b) and added to set P of FIG. 4 in step 28 (entry 28b), and the extended paths for nodes SAN[j] (e.g., N6 and N11) are added to set C in step 36 (entries 36b).
The mobile router N0 repeats the above described steps for each of the nodes. Hence, during the calculations for the nodes N3, N4, N5, N6, N7, N8, N9, N10, and N11, the respective least cost path entries Least_Path[i] are deleted from set C at respective events 24c, 24d, 24e, 24f, 24g, 24h, 24i, 24j, and 24k, and added to set P as respective entries 28c, 28d, 28e, 28f, 28g, 28h, 28i, 28j, and 28k. In addition, the mobile router N0 adds the respective extended path entries 36c, 36d, 36e, 36f, 36h, 36j, and 36j to Set C for nodes N3, N4, N5, N6, N8, N9, and N10. Note that there are no extended entries for N7 (adjacent nodes N0, N3 and N6 already belong in set K) or N11 (adjacent nodes N1, N2, N6, and N10 already belong in set K).
After the mobile router N0 has completed steps 24-40 for the last node (i=N) (e.g., N11), such that the set P of FIG. 4 contains the shortest path entries 28a, 28b, . . . 28k for the respective nodes N1, N2, . . . N11, the mobile router N0 discards the residual candidate paths in step 42 as illustrated in FIGS. 2 and 3. Hence, the set P of FIG. 4, upon completion of the SPF method of FIG. 2, provides reachability to the other network nodes as illustrated by the shortest path tree 12 of FIG. 5.
Numerous problems arise from implementing a Shortest Path First technique as illustrated above, especially since the candidate paths are discarded. For example, there is no guarantee of service during the convergence time, when a topological or a metric change occurs and before every node has resynchronized by recalculating a new tree.
Further, each and every node needs to assess the cost metrics in a consistent manner, even though the requirements for each node may be different. For example, a personal router operating on battery may prefer to prioritize a next hop that is reachable at low power, whereas a mobile node with an unlimited power supply may prefer to use a next hop router that is reachable at a low error rate.
Link reversal routing has been suggested as a technique for providing multiple communications links between nodes in an ad hoc mobile network, where link reversal routing algorithms build a directed acyclic graph (DAG) for each possible destination: a directed graph is acyclic if it contains no cycle or loop, and the DAG maps to a given destination based on the destination having only incoming links: all other nodes that have incoming links also must have outgoing links. An example of a routing algorithm that builds a DAG is the Temporally-Ordered Routing Algorithm (TORA).
Existing DAG-based routing algorithms that permit multiple connections, such as TORA, still require substantial processing and overhead requirements that may increase convergence times in response to topology changes, limiting the ad hoc network to rapidly respond to topological changes. For example, TORA requires that a packet is broadcast to all of its neighbors, resulting in additional congestion in the ad hoc network and additional processing by each network node that receives a packet and determines that the packet should be dropped.
Hence, if a network node configured for determining optimized routing connections (e.g., using Shortest Path First computations) was configured to also perform link reversal routing (in addition to the SPF computations) in order to perform load balancing across multiple paths, the requirement of performing both SPF computations in conjunction with link reversal routing computations would result in substantially higher performance requirements for the network node, resulting in a loss of performance or a more costly node having the additional processing capacity to perform the substantially higher performance requirements.